ftp.cs.arizona.edu/ftp.cs.arizona.edu.tar/ftp.cs.arizona.edu/icon/newsgrp/group98c.txt/000039_icon-group-sender _Thu Sep 17 12:33:59 1998.msg

Internet Message Format | 2000-09-20 | 4KB

Return-Path: <icon-group-sender>
Received: from kingfisher.CS.Arizona.EDU (kingfisher.CS.Arizona.EDU [192.12.69.239])
    by baskerville.CS.Arizona.EDU (8.9.1a/8.9.1) with SMTP id MAA18750
    for <[e-mail]>; Thu, 17 Sep 1998 12:33:57 -0700 (MST)
Received: by kingfisher.CS.Arizona.EDU (5.65v4.0/1.1.8.2/08Nov94-0446PM)
    id AA06376; Thu, 17 Sep 1998 12:33:28 -0700
To: [e-mail]
Date: Thu, 17 Sep 1998 10:58:59 -0400
From: Jerry Leichter <[e-mail]>
Message-Id: <[e-mail]>
Organization: System Management ARTS
Sender: [e-mail]
References: <[e-mail]>
Subject: Re: Context Switching
Errors-To: [e-mail]
Status: RO

There's been a great deal of work on this general issue in the Lisp
community.  In modern Lisp's there's the notion of a closure, which is a
function plus its execution context as an accessible object.  A co-
expression is the direct Icon analogue of a closure.  (A generator is a
restricted kind of co-expression which, because it is syntactically
bound to a particular point in the program, can be implemented more
efficiently.)

Implementing closures efficiently is challenging.  The "obvious"
implementation discards the use of a stack:  Function frames (which are
closures) are allocated from the heap, and garbage-collected just like
everything else.  If F call's G, then G's frame contains a return
pointer to F, so as long as G is around, F can't be discarded by the GC.
If the actual use of the code is just function calling, then once F
returns (implying that G has returned), F's frame is now garbage (the
only pointer is from G's frame, and *that* is now garbage).

In practice, this is too expensive to be practical.  So real implementa-
tions play games.  For example, they might allocate frames on the stack
and then copy them to the heap if one of a number of specialized calls -
which can, in effect, produce a user-accessible pointer to the frame -
are executed.  A cleverer example does this analysis in the compiler,
and allocates the frame on the stack or heap as required right at the
beginning, avoiding the copy.  Icon, in effect, uses this implementa-
tion:  The only way for a closure to be "captured" is by the use of a
coexpression creation, and the compiler can always recognize those.  The
big difference is that Icon assumes that most things are stack-based,
and produces efficient code on that assumption.  In a more aggressive
closure implementation, there's a stack pointer and a current closure
pointer, and code never uses the stack pointer to *find* the current
closure - it always uses the closure pointer, which may point into the
stack or into the heap.

There's even an interesting implementation technique - due to Henry
Baker, and intended for Lisp compilers that produce C code - which uses
the C stack, but in a total unconventional fashion:  Function calls are
done as always, *but they never return*.  Instead, to "return", you
restore the current closure (frame pointer) and PC from your caller,
*but you don't pop the stack*.  Of course, then your stack gets very
large after a while.  At that point, you garbage-collect it:  What's on
the stack is a whole bunch of stack frames, most of which are now
"dead", with no pointers to them.  You compact them out, sliding the
still-live frames down, and continue.

Lisp closures are much more general and powerful than Icon co-
expressions (much less generators).  What Icon got in returns was much
more efficient implementations (especially for generators, which are
comparable in cost to conventional function calls).  That tradeoff may
no longer be quite as necessary.
                            -- Jerry